import java.util.HashMap;
import java.util.Map;

class Solution{
    /**
     * 问题：值为k的连续子区间的个数
     * 链接：https://cn.bing.com/images/search?view=detailV2&ccid=8s4Fonxb&id=3ADEC73D5B45DF0825FAF6A4A70C49E5B828FC88&thid=OIP.8s4FonxbbkTONuHonh_xxAHaEr&mediaurl=https%3a%2f%2fc-ssl.dtstatic.com%2fuploads%2fitem%2f202001%2f02%2f20200102212411_etupp.thumb.1000_0.jpeg&exph=443&expw=700&q=%e5%8a%a8%e6%bc%ab%e8%83%8c%e6%99%af%e5%9b%be&FORM=IRPRST&ck=E264F040F7F57E3DCC6F710C884D0022&selectedIndex=33&itb=0&ajaxhist=0&ajaxserp=0
     * 时间复杂度：O(N);
     * 空间复杂度：O(N);
     */
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> hash = new HashMap<>();

        int sum = 0;int ret = 0;
        //第一个数就满足要求，区间不合法，需要先处理
        hash.put(0,1);

        for(int x : nums){
            sum += x;
            ret += hash.getOrDefault(sum - k,0);
            hash.put(sum,hash.getOrDefault(sum,0) + 1);
        }

        return ret;
    }
    /**
     * 问题：连续子数组可以被目标值整除的个数
     * 链接：https://leetcode.cn/problems/subarray-sums-divisible-by-k/
     * 时间复杂度：O(N);
     * 空间复杂度：O(N);
     */
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer,Integer> hash = new HashMap<Integer,Integer>();

        hash.put(0,1);
        int sum = 0,ret = 0;
        for(int x : nums){
            sum += x;
            int r = (sum % k + k) % k;

            ret += hash.getOrDefault(r,0);// + 1 + 2 + 3 + 1
            hash.put(r,hash.getOrDefault(r,0) + 1);
        }
        return ret;
    }

}